//========== Program Description ==========
//name : maze.java
//propose : figure out maze problem
//Written by akkz
//=========================================

public class Maze
{
	public int Maze[][] =
		{
			{ 1, 1, 1, 1, 1, 1, 1 },
			{ 1, 0, 1, 0, 0, 0, 1 },
			{ 1, 1, 0, 1, 1, 0, 1 },
			{ 1, 1, 0, 1, 1, 0, 1 },
			{ 1, 1, 1, 0, 1, 1, 1 },
			{ 1, 0, 0, 1, 0, 1, 1 },
			{ 1, 1, 1, 1, 0, 0, 1 },
			{ 1, 1, 1, 1, 1, 1, 1 } };

	public Maze( )
	{
		int i, j;

		System.out.println("== Problem of Maze ==");
		System.out.println("The Maze source is (1, 1).");
		System.out.println("The Maze Description is (6, 5).");
		Way(1, 1);

		System.out.println("The graph of Maze.");
		System.out.println(" \t0\t1\t2\t3\t4\t5\t6");
		System.out.println("");

		for (i = 0; i < 8; i++)
		{
			System.out.print("i\t");
			for (j = 0; j < 7; j++)
			{
				System.out.print(Maze[i][j] + "\t");
			}
			System.out.println();
			System.out.println();
		}
	}

	public boolean Way(int LocX, int LocY)
	{
		if (Maze[LocX][LocY] == 0)
		{
			Maze[LocX][LocY] = 2;

			if (Maze[6][5] == 2)
				return true;

			if (Way(LocX, LocY - 1))
				return true;
			else if (Way(LocX - 1, LocY - 1))
				return true;
			else if (Way(LocX + 1, LocY))
				return true;
			else if (Way(LocX - 1, LocY))
				return true;
			else if (Way(LocX, LocY + 1))
				return true;
			else if (Way(LocX + 1, LocY - 1))
				return true;
			else if (Way(LocX - 1, LocY + 1))
				return true;
			else if (Way(LocX + 1, LocY + 1))
				return true;
			else
			{
				Maze[LocX][LocY] = 3;
				return false;
			}
		} else
		{
			return false;
		}
	}
}
